#include <vector>
#include <stdexcept>
#include "../common/ListNode.h"

using namespace std;

/* 基于链表实现的队列 */
class LinkedListQueue {
private:
    ListNode *front, *rear;  // 头结点 front ，尾结点 rear 
    int queSize;

public:
    LinkedListQueue() {
        front = nullptr;
        rear = nullptr;
        queSize = 0;
    }

    ~LinkedListQueue() {
        freeMemoryLinkedList(front);
    }

    /* 获取队列的长度 */
    int size() {
        return queSize;
    }

    /* 判断队列是否为空 */
    bool empty() {
        return queSize == 0;
    }

    /* 入队 */
    void push(int num) {
        ListNode* node = new ListNode(num);
        if (front == nullptr) {
            front = node;
            rear = node;
        }
        else {
            rear->next = node;
            rear = node;
        }
        queSize++;
    }

    /* 出队 */
    void pop() {
        int num = peek();
        ListNode *tmp = front;
        front = front->next;
        delete tmp; 
        queSize--;
    }

    /* 访问队首元素 */
    int peek() {
        if (size() == 0)
            throw out_of_range("队列为空");
        return front->val;
    }

    /* 将链表转化为 Vector 并返回 */
    vector<int> toVector() {
        ListNode* node = front;
        vector<int> res(size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = node->val;
            node = node->next;
        }
        return res;
    }

    /* 遍历链表删除结点，释放内存 */
    void freeMemoryLinkedList(ListNode* head)
    {
        ListNode *pre, *cur = head;
        while (cur != nullptr) {
            pre = cur;
            cur = cur->next;
            delete pre;
        }
    }
};
